Passwords are the most common user authentication method, and they will most likely continue to be widely used. Although more secure authentication schemes have been suggested, such as using smartcards or public key cryptography none has gained the widespread adoption that passwords have in the consumer market. Yet passwords are inherently insecure, since the domain from which human passwords are chosen is typically rather small. An adversary can thus try to log into an account using all the most likely passwords until it finds the correct one.
Countermeasures that can be used against such attacks include:                (1) Timing: for example, given a login name/password pair, the server provides a slightly delayed yes/no answer, such as a no faster than one answer per second. This prevents an attacker from checking many passwords in a short amount of time.        (2) Account Locking: for example, after a few unsuccessful login attempts to a single account, the account is blocked. For example, an account could be blocked for an hour after unsuccessful attempts.        
The above-listed countermeasures may not be as effective when a potential attacker is not as interested in breaking into a specific account as he is concerned with breaking into any possible account. An attacker that tries to break into several accounts in parallel may be able to circumvent a timing countermeasure because user logins are typically handled by servers managing many login sessions in parallel. Therefore, the attacker tries logging into many accounts in parallel, trying multiple user name/password pairs per second. In addition, the account-locking feature may be circumvented since the attacker can try to log into an account using different user name/password pairs without using the same user name twice. Since each username is only used once or twice, the threshold for locking out a user based on failed login attempts is never triggered.
Attacking the account-locking countermeasure is further simplified since an attacker may be readily able to gain access to a large base of valid user names. A list of usernames is often known in interactive web communities, such as auction sites. In many large corporations user names equal the email handle and can just be grabbed off corporate web sites or employee lists. For large Internet services (e.g., MyYahoo) almost any reasonable user name has already been taken, i.e., valid user names are easy to guess for an attacker. The latter applies to any Internet service with a huge user base. Furthermore, valid bank account numbers are often easy to generate, as only part of them is random (parts of the account number are used to identify the branch, and one digit is used for a checksum). Thus, it is relatively easy to generate a valid user name for Internet banking services that use account numbers as user names.
Another major drawback of the account-locking feature is that it can create a denial of service attack against the user. These attacks are mounted by trying to login into a user's account several times with invalid password, thereby causing the account to be blocked. In the consumer space, there have been reports of denial of service attacks in auctions, where in the end phase (where most of the action happens), some users have managed to lock out competing bidders. In addition, the account locking feature is susceptible to inadvertent lockup, such as by users that do not type their passwords correctly. The service provider may need to maintain customer service centers to manage calls from users whose accounts have been locked up inadvertently, and the cost of running such services can be very expensive.
Broad password dictionary attacks generally require a large number of attempts, and thus need to be automated. The present invention makes it difficult or impossible to mount these automated attacks successfully with reasonable resources. In one embodiment, the security of the authentication scheme against “broad password attacks” does not require small lockout limits. For example, the lockout limit can be raised significantly, from 3 to 50 (or to any other suitable number, such as 500 or even higher). Moreover, this can be combined with timing methods—like requiring a 10 second window between two consecutive login attempts into the same account, such that denial of service attacks can not be performed in a few seconds. If the number of failed login attempts is counted at the server, a flag may be raised. A security administrator (or an automated program) can thus conclude with relative certainty that a denial of service attack has been attempted, and can be given more time to react.
Embodiments of the present invention thus provide for much better protection against denial of service attacks. Using the protocols set forth herein, the threshold that triggers an account to be locked up can be set to a very high value, without substantially affecting security.